package com.tju.eduservice.LeetCode;

import java.util.Arrays;
import java.util.NoSuchElementException;

public class MaxHeap {
    private int capacity;
    private int size = 0;
    private int[] array;
    public MaxHeap(int capacity){
        this.capacity = capacity;
        this.array = new int[capacity];
    }
    //获取左节点索引
    private int getLeftIndex(int parentIndex){
        return 2 * parentIndex + 1;
    }
    //获取右节点索引
    private int getRightIndex(int parentIndex){
        return 2 * parentIndex + 2;
    }
    //获取父节点索引
    private int getParentIndex(int childIndex){
        return (childIndex - 1) / 2;
    }
    //是否有左节点
    public boolean hasLeft(int index){
        return getLeftIndex(index) < size;
    }
    //是否有右节点
    public boolean hasRight(int index){
        return getRightIndex(index) < size;
    }
    //是否有父节点
    public boolean hasParent(int index){
        return getParentIndex(index) >= 0;
    }
    //获取左节点数据
    private int leftChild(int parentIndex){
        return array[getLeftIndex(parentIndex)];
    }
    //获取右节点数据
    private int rightChild(int parentIndex){
        return array[getRightIndex(parentIndex)];
    }
    //获取父节点数据
    private int getParent(int childIndex){
        return array[getParentIndex(childIndex)];
    }

    //插入操作
    public void insert(int value){
        if(size == capacity){
            array = Arrays.copyOf(array,capacity * 2);
            capacity = capacity << 1;
        }
        array[size] = value;
        size++;
        heapUp();
    }
    //上浮操作
    private void heapUp(){
        int index = size - 1;
        while (hasParent(index) && getParent(index) < array[index]){
            swap(getParentIndex(index),index);
            index = getParentIndex(index);
        }
    }

    //出队列poll操作
    private int poll(){
        if(size == 0){
            throw new NoSuchElementException("队列为空");
        }
        int value = array[0];
        array[0] = array[size - 1];//把最后一个元素放到上面
        size --;
        heapDown();
        return value;

    }
    private void heapDown(){
        int index = 0;
        while (hasLeft(index)){
            int largerChildIndex = getLeftIndex(index);
            if(hasRight(index) && rightChild(index) > leftChild(index)){
                largerChildIndex = getRightIndex(index);
            }
            if(array[index] < array[largerChildIndex]){
                swap(index,largerChildIndex);
            }else{
                break;
            }
            index = largerChildIndex;
        }
    }






    //交换两个index上的数据
    public void swap(int left,int right){
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}
